
Finding unusual review patterns using unexpected rules.

Detecting product review spammers using rating behaviors.

WePS3 Evaluation Campaign Overview of the On%2Dline Reputation Management Task.

A Remote Mirroring Architecture with Adaptively Cooperative Pipelining.

A Discuss of the Application of Project Management in the Non%2Dproject%2Dinvolved Organizations.

Hierarchical Web%2DPage Clustering via In%2DPage and Cross%2DPage Link Structures.

A Generalized Tree Matching Algorithm Considering Nested Lists for Web Data Extraction.

A highly linear wide dynamic range detector for cell recording with microelectrode arrays.

Entity relation discovery from web tables and links.
The World-Wide Web consists not only of a huge number of unstructured texts, but also a vast amount of valuable structured data. Web tables [2] are a typical type of structured information that are pervasive on the web, and Web-scale methods that automatically extract web tables have been studied extensively [1]. Many powerful systems (e.g., OCTOPUS [4], Mesa [3]) use extracted web tables as a fundamental component. In the database vernacular, a table is defined as a set of tuples which have the same attributes. Similarly, a web table is defined as a set of rows (corresponding to database tuples) which have the same column headers (corresponding to database attributes). Therefore, to extract a web table is to extract a relation on the web. In databases, tables often contain foreign keys which refer to other tables. Therefore, it follows that hyperlinks inside a web table sometimes function as foreign keys to other relations whose tuples are contained in the hyperlink’s target pages. In this paper, we explore this idea by asking: can we discover new attributes for web tables by exploring hyperlinks inside web tables? This poster proposes a solution that takes a web table as input. Frequent patterns are generated as new candidate relations by following hyperlinks in the web table. The confidence of candidates are evaluated, and trustworthy candidates are selected to become new attributes for the table. Finally, we show the usefulness of our method by performing experiments on a variety of web domains.
The dynamics of pest control pollution model with age structure and time delay.

Dynamical Jumping Real%2DTime Fault%2DTolerant Routing Protocol for Wireless Sensor Networks

What%27s behind topic formation and development a perspective of community core groups.

Probabilistic Approximations of Signaling Pathway Dynamics.

Semantic%2DBased Remote Sensing Images Intelligent Service on Grid Environment.

Sentiment Analysis of Conditional Sentences.
This paper studies sentiment analysis of conditional sentences. The aim is to determine whether opinions expressed on different topics in a conditional sentence are positive, negative or neutral. Conditional sentences are one of the commonly used language constructs in text. In a typical document, there are around 8 % of such sentences. Due to the condition clause, sentiments expressed in a conditional sentence can be hard to determine. For example, in the sentence, if your Nokia phone is not good, buy this great Samsung phone, the author is positive about “Samsung phone ” but does not express an opinion on “Nokia phone ” (although the owner of the “Nokia phone ” may be negative about it). However, if the sentence does not have “if”, the first clause is clearly negative. Although “if ” commonly signifies a conditional sentence, there are many other words and constructs that can express conditions. This paper first presents a linguistic analysis of such sentences, and then builds some supervised learning models to determine if sentiments expressed on different topics in a conditional sentence are positive, negative or neutral. Experimental results on conditional sentences from 5 diverse domains are given to demonstrate the effectiveness of the proposed approach. 1
An Ontology%2DBased Approach to Knowledge Management.
Most enterprises agree that knowledge is an  essential asset for success and survival on a  increasingly competitive and global market.  This awareness is one of the main reasons for  the exponential growth of knowledge management  in the past decade. Our approach to  knowledge management is based on ontologies,  and makes knowledge assets intelligently  accessible to people in organizations. Most  company-vital knowledge resides in the heads  of people, and thus successful knowledge management  does not only consider technical aspects,  but also social ones. In this paper, we  describe an approach to intelligent knowledge  management that explicitly takes into account  the social issues involved. The proof of concept  is given by a large-scale initiative involving  knowledge management of a virtual organization. 
Towards the SocioScope an information system for the study of social dynamics through digital traces.
Digital traces, social dynamics Over the past decade there has been an explosion in the deployment of pervasive systems like cell phone networks and content aggregators on the Internet that produce massive amounts of data as by-products of their interaction with users. This data is related to the actions and opinions of people and thereby to the overall dynamics of cities, how they function and evolve over time. Here we propose the implementation of a new information system, the SocioScope, that streamlines the operations of data gathering and data storage and that supports the diverse needs of the research community, local authorities, enterprises, and citizens. Our SocioScope allows for the collection, integration, and study of different types of spatiotemporal data. We present two use cases and an analysis of the requirements for the system. We introduce the multi-tier architecture that supports data gathering, storage, integration, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
Finding Actionable Knowledge via Automated Comparison.

Expanding Domain Sentiment Lexicon through Double Propagation.
In most sentiment analysis applications, the sentiment lexicon plays a key role. However, it is hard, if not impossible, to collect and maintain a universal sentiment lexicon for all application domains because different words may be used in different domains. The main existing technique extracts such sentiment words from a large domain corpus based on different conjunctions and the idea of sentiment coherency in a sentence. In this paper, we propose a novel propagation approach that exploits the relations between sentiment words and topics or product features that the sentiment words modify, and also sentiment words and product features themselves to extract new sentiment words. As the method propagates information through both sentiment words and features, we call it double propagation. The extraction rules are designed based on relations described in dependency trees. A new method is also proposed to assign polarities to newly discovered sentiment words in a domain. Experimental results show that our approach is able to extract a large number of new sentiment words. The polarity assignment method is also effective. 
A Heuristic Greedy Optimum Algorithm for Target Coverage in Wireless Sensor Networks.

An New Global Dynamic Scheduling Algorithm with Multi%2DHop Path Splitting and Multi%2DPathing Using GridFTP.

Positive Unlabeled Learning for Data Stream Classification.

Opinion Mining.
An important part of our information-gathering behavior has always been to find out what other people think. With the growing availability and popularity of opinion-rich resources such as online review sites and personal blogs, new opportunities and challenges arise as people now can, and do, actively use information technologies to seek out and understand the opinions of others. The sudden eruption of activity in the area of opinion mining and sentiment analysis, which deals with the computational treatment of opinion, sentiment, and subjectivity in text, has thus occurred at least in part as a direct response to the surge of interest in new systems that deal directly with opinions as a first-class object. This survey covers techniques and approaches that promise to directly enable opinion-oriented information-seeking systems. Our focus is on methods that seek to address the new challenges raised by sentiment-aware applications, as compared to those that are already present in more traditional fact-based analysis. We include materialon summarization of evaluative text and on broader issues regarding privacy, manipulation, and economic impact that the development of opinion-oriented information-access services gives rise to. To facilitate future work, a discussion of available resources, benchmark datasets, and evaluation campaigns is also provided. 1
Classification by Association Rule Analysis.
In this paper, we discuss the potential applications of data mining techniques for the design of Web based information retrieval support systems (IRSS). In particular, we apply clustering methods for the granulation of di#erent entities involved in IRSS. Two types of granulations, single-level and multi-level granulations, are investigated. Issues of document space granulation, query space granulation, term space granulation, and retrieval results granulation are studied in detail. It is demonstrated that each di#erent granulation supports a di#erent user task.

A singular integral of the composite operator.


Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Towards a Multi%2Dagent Model for Planning and Design of Exposition Spaces.

Mining Opinions in Comparative Sentences.
This paper studies sentiment analysis from the user-generated content on the Web. In particular, it focuses on mining opinions from comparative sentences, i.e., to determine which entities in a comparison are preferred by its author. A typical comparative sentence compares two or more entities. For example, the sentence, “the picture quality of Camera X is better than that of Camera Y”, compares two entities “Camera X ” and “Camera Y” with regard to their picture quality. Clearly, “Camera X ” is the preferred entity. Existing research has studied the problem of extracting some key elements in a comparative sentence. However, there is still no study of mining opinions from comparative sentences, i.e., identifying preferred entities of the author. This paper studies this problem, and proposes a technique to solve the problem. Our experiments using comparative sentences from product reviews and forum posts show that the approach is effective. 1
Opinion spam and analysis.
Evaluative texts on the Web have become a valuable source of opinions on products, services, events, individuals, etc. Recently, many researchers have studied such opinion sources as product reviews, forum posts, and blogs. However, existing research has been focused on classification and summarization of opinions using natural language processing and data mining techniques. An important issue that has been neglected so far is opinion spam or trustworthiness of online opinions. In this paper, we study this issue in the context of product reviews, which are opinion rich and are widely used by consumers and product manufacturers. In the past two years, several startup companies also appeared which aggregate opinions from product reviews. It is thus high time to study spam in reviews. To the best of our knowledge, there is still no published study on this topic, although Web spam and email spam have been investigated extensively. We will see that opinion spam is quite different from Web spam and email spam, and thus requires different detection techniques. Based on the analysis of 5.8 million reviews and 2.14 million reviewers from amazon.com, we show that opinion spam in reviews is widespread. This paper analyzes such spam activities and presents some novel techniques to detect them.
Time Sensitive Ranking with Application to Publication Search.

Opinion spam and analysis.
Evaluative texts on the Web have become a valuable source of opinions on products, services, events, individuals, etc. Recently, many researchers have studied such opinion sources as product reviews, forum posts, and blogs. However, existing research has been focused on classification and summarization of opinions using natural language processing and data mining techniques. An important issue that has been neglected so far is opinion spam or trustworthiness of online opinions. In this paper, we study this issue in the context of product reviews, which are opinion rich and are widely used by consumers and product manufacturers. In the past two years, several startup companies also appeared which aggregate opinions from product reviews. It is thus high time to study spam in reviews. To the best of our knowledge, there is still no published study on this topic, although Web spam and email spam have been investigated extensively. We will see that opinion spam is quite different from Web spam and email spam, and thus requires different detection techniques. Based on the analysis of 5.8 million reviews and 2.14 million reviewers from amazon.com, we show that opinion spam in reviews is widespread. This paper analyzes such spam activities and presents some novel techniques to detect them.
A holistic lexicon%2Dbased approach to opinion mining.
One of the important types of information on the Web is the opinions expressed in the user generated content, e.g., customer reviews of products, forum posts, and blogs. In this paper, we focus on customer reviews of products. In particular, we study the problem of determining the semantic orientations (positive, negative or neutral) of opinions expressed on product features in reviews. This problem has many applications, e.g., opinion mining, summarization and search. Most existing techniques utilize a list of opinion (bearing) words (also called opinion lexicon) for the purpose. Opinion words are words that express desirable (e.g., great, amazing, etc.) or undesirable (e.g., bad, poor, etc) states. These approaches, however, all have some major shortcomings. In this paper, we propose a holistic lexicon-based approach to solving the problem by exploiting external evidences and linguistic conventions of natural language expressions. This approach allows the system to handle opinion words that are context dependent, which cause major difficulties for existing algorithms. It also deals with many special words, phrases and language constructs which have impacts on opinions based on their linguistic patterns. It also has an effective function for aggregating multiple conflicting opinion words in a sentence. A system, called Opinion Observer, based on the proposed technique has been implemented. Experimental results using a benchmark product review data set and some additional reviews show that the proposed technique is highly effective. It outperforms existing methods significantly.
Managing large collections of data mining models.

Systematic benchmarking of microarray data feature extraction and classification.

Top 10 algorithms in data mining.
Abstract This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. These top 10 algorithms are among the most influential data mining algorithms in the research community. With each algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and review current and further research on the algorithm. These 10 algorithms cover classification,
Guest editorial.
of vital signs, and medical emergency teams
Guest editorial.
of vital signs, and medical emergency teams


Learning to Classify Documents with Only a Small Positive Training Set.

Analyzing and Detecting Review Spam.

Learning to Identify Unexpected Instances in the Test Set.

Semantic Text Classification of Emergent Disease Reports.

Semantic text classification of disease reporting.

The utility of linguistic rules in opinion mining.

Review spam detection.
Evaluative texts on the Web have become a valuable source of opinions on products, services, events, individuals, etc. Recently, many researchers have studied such opinion sources as product reviews, forum posts, and blogs. However, existing research has been focused on classification and summarization of opinions using natural language processing and data mining techniques. An important issue that has been neglected so far is opinion spam or trustworthiness of online opinions. In this paper, we study this issue in the context of product reviews, which are opinion rich and are widely used by consumers and product manufacturers. In the past two years, several startup companies also appeared which aggregate opinions from product reviews. It is thus high time to study spam in reviews. To the best of our knowledge, there is still no published study on this topic, although Web spam and email spam have been investigated extensively. We will see that opinion spam is quite different from Web spam and email spam, and thus requires different detection techniques. Based on the analysis of 5.8 million reviews and 2.14 million reviewers from amazon.com, we show that opinion spam in reviews is widespread. This paper analyzes such spam activities and presents some novel techniques to detect them.
KDD Cup and workshop 2007.
In October, 2006 Netflix released a dataset containing 100 million anonymous movie ratings and challenged the data mining, machine learning and computer science communities to develop systems that could beat the accuracy of its recommendation system, Cinematch. We briefly describe the challenge itself, review related work and efforts, and summarize visible progress to date. Other potential uses of the data are outlined, including its application to the KDD Cup 2007.
Extracting Web Data Using Instance%2DBased Learning.
Abstract. This paper studies structured data extraction from Web pages, e.g., online product description pages. Existing approaches to data extraction include wrapper induction and automatic methods. In this paper, we propose an instance-based learning method, which performs extraction by comparing each new instance (or page) to be extracted with labeled instances (or pages). The key advantage of our method is that it does not need an initial set of labeled pages to learn extraction rules as in wrapper induction. Instead, the algorithm is able to start extraction from a single labeled instance (or page). Only when a new page cannot be extracted does the page need labeling. This avoids unnecessary page labeling, which solves a major problem with inductive learning (or wrapper induction), i.e., the set of labeled pages may not be representative of all other pages. The instance-based approach is very natural because structured data on the Web usually follow some fixed templates and pages of the same template usually can be extracted using a single page instance of the template. The key issue is the similarity or distance measure. Traditional measures based on the Euclidean distance or text similarity are not easily applicable in this context because items to be extracted from different pages can be entirely different. This paper proposes a novel similarity measure for the purpose, which is suitable for templated Web pages. Experimental results with product data extraction from 1200 pages in 24 diverse Web sites show that the approach is surprisingly effective. It outperforms the state-of-the-art existing systems significantly. 1
The Optimal Pulse harvesting Policy on a Single%2DSpecies Population Model with Birth Pulses in a polluted Environment.

KDD Cup and workshop 2007.
In October, 2006 Netflix released a dataset containing 100 million anonymous movie ratings and challenged the data mining, machine learning and computer science communities to develop systems that could beat the accuracy of its recommendation system, Cinematch. We briefly describe the challenge itself, review related work and efforts, and summarize visible progress to date. Other potential uses of the data are outlined, including its application to the KDD Cup 2007.
Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management

Advances in Web Mining and Web Usage Analysis

Automatic Wrapper Generation Using Tree Matching and Partial Tree Alignment.

Mining Comparative Sentences and Relations.

Opinion Extraction and Summarization on the Web.

Opportunity map identifying causes of failure %2D a deployed data mining system.

Mining Latent Associations of Objects Using a Typed Mixture Model%2D%2DA Case Study on Expert%2FExpertise Mining.

Rule interestingness analysis using OLAP operations.
The problem of interestingness of discovered rules has been investigated by many researchers. The issue is that data mining algorithms often generate too many rules, which make it very hard for the user to find the interesting ones. Over the years many techniques have been proposed. However, few have made it to real-life applications. Since August 2004, we have been working on a major application for Motorola. The objective is to find causes of cellular phone call failures from a large amount of usage log data. Class association rules have been shown to be suitable for this type of diagnostic data mining application. We were also able to put several existing interestingness methods to the test, which revealed some major shortcomings. One of the main problems is that most existing methods treat rules individually. However, we discovered that users seldom regard a single rule to be interesting by itself. A rule is only interesting in the context of some other rules. Furthermore, in many cases, each individual rule may not be interesting, but a group of them together can represent an important piece of knowledge. This led us to discover a deficiency of the current rule mining paradigm. Using non-zero minimum support and non-zero minimum confidence eliminates a large amount of context information, which makes rule analysis difficult. This paper proposes a novel approach to deal with all of these issues, which casts rule analysis as OLAP operations and general impression mining. This approach enables the user to explore the knowledge space to find useful knowledge easily and systematically. It also provides a natural framework for visualization. As an evidence of its effectiveness, our system, called Opportunity Map, based on these ideas has been deployed, and it is in daily use in Motorola for finding actionable knowledge from its engineering and other types of data sets.
Opportunity map identifying causes of failure %2D a deployed data mining system.

Discovering Overlapping Communities of Named Entities.
Abstract. Although community discovery based on social network analysis has been studied extensively in the Web hyperlink environment, limited research has been done in the case of named entities in text documents. The cooccurrence of entities in documents usually implies some connections among them. Investigating such connections can reveal important patterns. In this paper, we mine communities among named entities in Web documents and text corpus. Most existing works on community discovery generate a partition of the entity network, assuming each entity belongs to one community. However, in the scenario of named entities, an entity may participate in several communities. For example, a person is in the communities of his/her family, colleagues, and friends. In this paper, we propose a novel technique to mine overlapping communities of named entities. This technique is based on triangle formation, expansion, and clustering with content similarity. Our experimental results show that the proposed technique is highly effective.
A Bottom%2DUp Distance%2DBased Index Tree for Metric Space.

Subsequence Similarity Search Under Time Shifting.

Identifying comparative sentences in text documents.
This paper studies the problem of identifying comparative sentences in text documents. The problem is related to but quite different from sentiment/opinion sentence identification or classification. Sentiment classification studies the problem of classifying a document or a sentence based on the subjective opinion of the author. An important application area of sentiment/opinion identification is business intelligence as a product manufacturer always wants to know consumers ’ opinions on its products. Comparisons on the other hand can be subjective or objective. Furthermore, a comparison is not concerned with an object in isolation. Instead, it compares the object with others. An example opinion sentence is “the sound quality of CD player X is poor”. An example comparative sentence is “the sound quality of CD player X is not as good as that of CD player Y”. Clearly, these two sentences give different information. Their language constructs are quite different too. Identifying comparative sentences is also useful in practice because direct comparisons are perhaps one of the most convincing ways of evaluation, which may even be more important than opinions on each individual object. This paper proposes to study the comparative sentence identification problem. It first categorizes comparative sentences into different types, and then presents a novel integrated pattern discovery and supervised learning approach to identifying comparative sentences from text documents. Experiment results using three types of documents, news articles, consumer reviews of products, and Internet forum postings, show a precision of 79% and recall of 81%. More detailed results are given in the paper.
An Effective Approach for Hiding Sensitive Knowledge in Data Publishing.



Dynamic Incremental Data Summarization for Hierarchical Clustering.

Tight Bounds on the Estimation Distance Using Wavelet.

Structured Data Extraction from the Web Based on Partial Tree Alignment.

Mining community structure of named entities from free text.
Although community discovery based on social network has been studied extensively in the Web hyperlink environment, limited research has been done in the case of Web documents. The co-occurrence of Words and entities in sentences and documents usually implies some connections among them. Studying such connections may reveal important relationships. In this paper, we investigate the cooccurrences of named entities in Web pages and blogs, and mine communities among those entities. We show that identifying communities in such an environment can be transformed into a graph clustering problem. A hierarchical clustering algorithm is then proposed, which exploits triangle structures within the graph and the mutual information between vertices. Our empirical study shows that the proposed algorithm is promising in discovering communities from Web documents.
Opportunity map a visualization framework for fast identification of actionable knowledge.
Data mining techniques frequently find a large number of patterns or rules, which make it very difficult for a human analyst to interpret the results and to find the truly interesting and actionable rules. Due to the subjective nature of &amp;quot;interestingness&amp;quot;, human involvement in the analysis process is crucial. In this paper, we propose a novel visual data mining framework for the purpose of identifying actionable knowledge quickly and easily from discovered rules and data. This framework is called the Opportunity Map. It is inspired by some interesting ideas from Quality Engineering, in particular Quality Function Deployment (QFD) and the House of Quality. It associates summarized data or discovered rules with the application objective using an interactive matrix, which enables the user to quickly identify where the opportunities are. The proposed system can be used to visually analyze discovered rules, and other statistical properties of the data. The user can also interactively group actionable attributes and values, and see how they affect the targets of interest. Combined with drill-down and comparative analysis, the user can analyze rules and data at different levels of detail. The proposed visualization framework thus represents a systematic and yet flexible method of rule analysis. Applications of the system to large-scale data sets from our industrial partner have yielded promising results.
Incorporating with Recursive Model Training in Time Series Clustering.

Non%2DAlmost%2DDerivable Frequent Itemsets Mining.

A Formal Specification for Web Services Composition and Verification.

Controlling FD and MVD Inferences in MLS.

Assigning Unique Keys to Chemical Compounds for Data Integration Some Interesting Counter Examples.
Integrating data involving chemical structures is simplified when unique identifiers (UIDs) can be associated with chemical structures. For example, these identifiers can be used as database keys. One common approach is to use the Unique SMILES notation introduced in [2]. The Unique SMILES views a chemical structure as a graph with atoms as nodes and bonds as edges and uses a depth first traversal of the graph to generate the SMILES strings. The algorithm establishes a node ordering by using certain symmetry properties of the graphs. In this paper, we present certain molecular graphs for which the algorithm fails to generate UIDs. Indeed, we show that different graphs in the same symmetry class employed by the Unique SMILES algorithm have different Unique SMILES IDs. We tested the algorithm on the National Cancer Institute (NCI) database [7] and found several molecular structures for which the algorithm also failed. We have also written a python script that generates molecular graphs for which the algorithm fails.
Learning from Positive and Unlabeled Examples with Different Data Distributions.
Abstract. We study the problem of learning from positive and unlabeled examples. Although several techniques exist for dealing with this problem, they all assume that positive examples in the positive set P and the positive examples in the unlabeled set U are generated from the same distribution. This assumption may be violated in practice. For example, one wants to collect all printer pages from the Web. One can use the printer pages from one site as the set P of positive pages and use product pages from another site as U. One wants to classify the pages in U into printer pages and non-printer pages. Although printer pages from the two sites have many similarities, they can also be quite different because different sites often present similar products in different styles and have different focuses. In such cases, existing methods perform poorly. This paper proposes a novel technique A-EM to deal with the problem. Experiment results with product page classification demonstrate the effectiveness of the proposed technique. 1
Classification using support vector machines with graded resolution.

A Visual Data Mining Framework for Convenient Identification of Useful Knowledge.

A Small Listener for Heterogeneous Mobile Devices A Service Enabler with a Uniform Web Object View.

On the Universal Approximation Theorem of Fuzzy Neural Networks with Random Membership Function Parameters.

Extracting Web Data Using Instance%2DBased Learning.
Abstract. This paper studies structured data extraction from Web pages, e.g., online product description pages. Existing approaches to data extraction include wrapper induction and automatic methods. In this paper, we propose an instance-based learning method, which performs extraction by comparing each new instance (or page) to be extracted with labeled instances (or pages). The key advantage of our method is that it does not need an initial set of labeled pages to learn extraction rules as in wrapper induction. Instead, the algorithm is able to start extraction from a single labeled instance (or page). Only when a new page cannot be extracted does the page need labeling. This avoids unnecessary page labeling, which solves a major problem with inductive learning (or wrapper induction), i.e., the set of labeled pages may not be representative of all other pages. The instance-based approach is very natural because structured data on the Web usually follow some fixed templates and pages of the same template usually can be extracted using a single page instance of the template. The key issue is the similarity or distance measure. Traditional measures based on the Euclidean distance or text similarity are not easily applicable in this context because items to be extracted from different pages can be entirely different. This paper proposes a novel similarity measure for the purpose, which is suitable for templated Web pages. Experimental results with product data extraction from 1200 pages in 24 diverse Web sites show that the approach is surprisingly effective. It outperforms the state-of-the-art existing systems significantly. 1
NET %2D A System for Extracting Web Data from Flat and Nested Data Records.
Abstract. This paper studies automatic extraction of structured data from Web pages. Each of such pages may contain several groups of structured data records. Existing automatic methods still have several limitations. In this paper, we propose a more effective method for the task. Given a page, our method first builds a tag tree based on visual information. It then performs a post-order traversal of the tree and matches subtrees in the process using a tree edit distance method and visual cues. After the process ends, data records are found and data items in them are aligned and extracted. The method can extract data from both flat and nested data records. Experimental evaluation shows that the method performs the extraction task accurately. 1
WISE%2D2005 Tutorial Web Content Mining.

Opinion observer analyzing and comparing opinions on the Web.
The Web has become an excellent source for gathering consumer opinions. There are now numerous Web sites containing such opinions, e.g., customer reviews of products, forums, discussion groups, and blogs. This paper focuses on online customer reviews of products. It makes two contributions. First, it proposes a novel framework for analyzing and comparing consumer opinions of competing products. A prototype system called Opinion Observer is also implemented. The system is such that with a single glance of its visualization, the user is able to clearly see the strengths and weaknesses of each product in the minds of consumers in terms of various product features. This comparison is useful to both potential customers and product manufacturers. For a potential customer, he/she can see a visual side-by-side and feature-by-feature comparison of consumer opinions on these products, which helps him/her to decide which product to buy. For a product manufacturer, the comparison enables it to easily gather marketing intelligence and product benchmarking information. Second, a new technique based on language pattern mining is proposed to extract product features from Pros and Cons in a particular type of reviews. Such features form the basis for the above comparison. Experimental results show that the technique is highly effective and outperform existing methods significantly.
Web data extraction based on partial tree alignment.
This paper studies the problem of extracting data from a Web page that contains several structured data records. The objective is to segment these data records, extract data items/fields from them and put the data in a database table. This problem has been studied by several researchers. However, existing methods still have some serious limitations. The first class of methods is based on machine learning, which requires human labeling of many examples from each Web site that one is interested in extracting data from. The process is time consuming due to the large number of sites and pages on the Web. The second class of algorithms is based on automatic pattern discovery. These methods are either inaccurate or make many assumptions. This paper proposes a new method to perform the task automatically. It consists of two steps, (1) identifying individual data records in a page, and (2) aligning and extracting data items from the identified data records. For step 1, we propose a method based on visual information to segment data records, which is more accurate than existing methods. For step 2, we propose a novel partial alignment technique based on tree matching. Partial alignment means that we align only those data fields in a pair of data records that can be aligned (or matched) with certainty, and make no commitment on the rest of the data fields. This approach enables very accurate alignment of multiple data records. Experimental results using a large number of Web pages from diverse domains show that the proposed two-step technique is able to segment data records, align and extract data from them very accurately.
An EM Based Training Algorithm for Cross%2DLanguage Text Categorization.
Due to the globalization on the Web, many companies and institutions need to efficiently organize and search repositories containing multilingual documents. The management of these heterogeneous text collections increases the costs significantly because experts of different languages are required to organize these collections. Cross-Language Text Categorization can provide techniques to extend existing automatic classification systems in one language to new languages without requiring additional intervention of human experts. In this paper we propose a learning algorithm based on the EM scheme which can be used to train text classifiers in a multilingual environment. In particular, in the proposed approach, we assume that a predefined category set and a collection of labeled training data is available for a given language L1. A classifier for a different language L2 is trained by translating the available labeled training set for L1 to L2 and by using an additional set of unlabeled documents from L2. This technique allows us to extract correct statistical properties of the language L2 which are not completely available in automatically translated examples, because of the different characteristics of language L1 and of the approximation of the translation process. Our experimental results show that the performance of the proposed method is very promising when applied on a test document set extracted from newsgroups in English and Italian. 1
Adding the Temporal Dimension to Search %2D A Case Study in Publication Search.

The dynamics of a prey%2Ddependent consumption model concerning impulsive control strategy.

Characterizing the dynamic connectivity between genes by variable parameter regression and Kalman filtering based on temporal gene expression data.

Dynamic Complexities in a Lotka%2Dvolterra Predator%2Dprey Model Concerning impulsive Control Strategy.

Guest Editors%27 Introduction Special Section on Intelligent Data Preparation.

SARS%2DCoV protease inhibitors design using virtual screening method from natural products libraries.

Proceedings of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery

Text Classification by Labeling Words.
Traditionally, text classifiers are built from labeled training examples. Labeling is usually done manually by human experts (or the users), which is a labor intensive and time consuming process. In the past few years, researchers investigated various forms of semi-supervised learning to reduce the burden of manual labeling. In this paper, we propose a different approach. Instead of labeling a set of documents, the proposed method labels a set of representative words for each class. It then uses these words to extract a set of documents for each class from a set of unlabeled documents to form the initial training set. The EM algorithm is then applied to build the classifier. The key issue of the approach is how to obtain a set of representative words for each class. One way is to ask the user to provide them, which is difficult because the user usually can only give a few words (which are insufficient for accurate learning). We propose a method to solve the problem. It combines clustering and feature selection. The technique can effectively rank the words in the unlabeled set according to their importance. The user then selects/labels some words from the ranked list for each class. This process requires less effort than providing words with no help or manual labeling of documents. Our results show that the new method is highly effective and promising.
Mining Opinion Features in Customer Reviews.

A Novel RBF Neural Network with Fast Training and Accurate Generalization.

Semi%2Dsupervised Text Classification Using Partitioned EM.
Abstract. Text classification using a small labeled set and a large unlabeled data is seen as a promising technique to reduce the labor-intensive and time consuming effort of labeling training data in order to build accurate classifiers since unlabeled data is easy to get from the Web. In [16] it has been demonstrated that an unlabeled set improves classification accuracy significantly with only a small labeled training set. However, the Bayesian method used in [16] assumes that text documents are generated from a mixture model and there is a one-to-one correspondence between the mixture components and the classes. This may not be the case in many applications. In many real-life applications, a class may cover documents from many different topics, which violates the oneto-one correspondence assumption. In such cases, the resulting classifiers can be quite poor. In this paper, we propose a clustering based partitioning technique to solve the problem. This method first partitions the training documents in a hierarchical fashion using hard clustering. After running the expectation maximization (EM) algorithm in each partition, it prunes the tree using the labeled data. The remaining tree nodes or partitions are likely to satisfy the oneto-one correspondence condition. Extensive experiments demonstrate that this method is able to achieve a dramatic gain in classification performance.
A Novel Fuzzy Neural Network with Fast Training and Accurate Generalization.

Mining and summarizing customer reviews.

V%2DMiner using enhanced parallel coordinates to mine product design and test data.
Analyzing data to find trends, correlations, and stable patterns is an important task in many industrial applications. This paper proposes a new technique based on parallel coordinate visualization. Previous work on parallel coordinate methods has shown that they are effective only when variables that are correlated and/or show similar patterns are displayed adjacently. Although current parallel coordinate tools allow the user to manually rearrange the order of variables, this process is very time-consuming when the number of variables is large. Automated assistance is required. This paper introduces an editdistance based technique to rearrange variables so that interesting change patterns can be easily detected visually. The Visual Miner (V-Miner) software includes both automated methods for visualizing common patterns and a query tool that enables the user to describe specific target patterns to be mined or displayed by the system. In addition, the system can filter data according to rules sets imported from other data mining tools. This feature was found very helpful in practice, because it enables decision makers to visually identify interesting rules and data segments for further analysis or data mining. This paper begins with an introduction to the proposed techniques and the V-Miner system. Next, a case study illustrates how V-Miner has been used at Motorola to guide product design and test decisions.
A note on a nonlocal boundary value problems.

SyD A Middleware Testbed for Collaborative Applications over Small Heterogeneous Devices and Data Stores.

Dealing with different distributions in learning from.

On the temporal dimension of search.
Web search is probably the single most important application on the Internet. The most famous search techniques are perhaps the PageRank and HITS algorithms. These algorithms are motivated by the observation that a hyperlink from a page to another is an implicit conveyance of authority to the target page. They exploit this social phenomenon to identify quality pages, e.g., &#034;authority&#034; pages and &#034;hub&#034; pages. In this paper we argue that these algorithms miss an important dimension of the Web, the temporal dimension. The Web is not a static environment. It changes constantly. Quality pages in the past may not be quality pages now or in the future. These techniques favor older pages because these pages have many in-links accumulated over time. New pages, which may be of high quality, have few or no inlinks and are left behind. Bringing new and quality pages to users is important because most users want the latest information. Research publication search has exactly the same problem. This paper studies the temporal dimension of search in the context of research publication search. We propose a number of methods deal with the problem. Our experimental results show that these methods are highly effective.
Existence and uniqueness of solutionsto first%2Dorder multipoint boundary value problems.

Positive solutions of three%2Dpoint boundary value problems for the one%2Ddimensional p%2Dlaplacian with infinitely many singularities.

A note on a nonlocal boundary value problems.


Positive solutions of a nonlinear four%2Dpoint boundary value problems.


Esub8 A novel tool to predict protein subcellular localizations in eukaryotic organisms.

Mining Web Pages for Data Records.
M i n i n g t h e W e b Data mining to extract information from Web pages can help provide value-added services.
Guest Editors%27 Introduction Special Section on Mining and Searching the Web.

An Empirical Study of the Universal Chemical Key Algorithm for Assigning Unique Keys to Chemical Compounds.

Editorial special issue on web content mining.
With the phenomenal growth of the Web, there is an everincreasing volume of data and information published in numerous Web pages. The research in Web mining aims to develop new techniques to effectively extract and mine useful knowledge or
WebKDD 2004 web mining and web usage analysis post%2Dworkshop report.

Experimental Studies of the Universal Chemical Key %28UCK%29Algorithm on the NCI Database of Chemical Compounds.
We have developed an algorithm called the Universal Chemical Key (UCK) algorithm that constructs a unique key for a molecular structure. The molecular structures are represented as undirected labeled graphs with the atoms representing the vertices of the graph and the bonds representing the edges. The algorithm was tested on 236,917 compounds obtained from the National Cancer Institute (NCI) database of chemical compounds. In this paper we present the algorithm, some examples and the experimental results on the NCI database. On the NCI database, the UCK algorithm provided distinct unique keys for chemicals with different molecular structures. 1.
Building Text Classifiers Using Positive and Unlabeled Examples.
This paper studies the problem of building text classifiers using positive and unlabeled examples. The key feature of this problem is that there is no negative example for learning. Recently, a few techniques for solving this problem were proposed in the literature. These techniques are based on the same idea, which builds a classifier in two steps. Each existing technique uses a different method for each step. In this paper, we first introduce some new methods for the two steps, and perform a comprehensive evaluation of all possible combinations of methods of the two steps. We then propose a more principled approach to solving the problem based on a biased formulation of SVM, and show experimentally that it is more accurate than the existing techniques. 1.
Detecting Patterns of Change Using Enhanced Parallel Coordinates Visualization.

Learning with Positive and Unlabeled Examples Using Weighted Logistic Regression.
The problem of learning with positive and unlabeled  examples arises frequently in retrieval applications.
Web Page Cleaning for Web Mining through Feature Weighting.
Unlike conventional data or text, Web pages typically contain a large amount of information that is not part of the main contents of the pages, e.g., banner ads, navigation bars, and copyright notices. Such irrelevant information (which we call Web page noise) in Web pages can seriously harm Web mining, e.g., clustering and classification. In this paper, we propose a novel feature weighting technique to deal with Web page noise to enhance Web mining. This method first builds a compressed structure tree to capture the common structure and comparable blocks in a set of Web pages. It then uses an information based measure to evaluate the importance of each node in the compressed structure tree. Based on the tree and its node importance values, our method assigns a weight to each word feature in its content block. The resulting weights are used in Web mining. We evaluated the proposed technique with two Web mining tasks, Web page clustering and Web page classification. Experimental results show that our weighting method is able to dramatically improve the mining results. 1
Learning to Classify Texts Using Positive and Unlabeled Data.
In traditional text classification, a classifier is built using labeled training documents of every class. This paper studies a different problem. Given a set P of documents of a particular class (called positive class) and a set U of unlabeled documents that contains documents from class P and also other types of documents (called negative class documents), we want to build a classifier to classify the documents in U into documents from P and documents not from P. The key feature of this problem is that there is no labeled negative document, which makes traditional text classification techniques inapplicable. In this paper, we propose an effective technique to solve the problem. It combines the Rocchio method and the SVM technique for classifier building. Experimental results show that the new method outperforms existing methods significantly. 1
ECO An Empirical%2DBased Compilation and Optimization System.

Eliminating noisy information in Web pages for data mining.
A commercial Web page typically contains many information  blocks. Apart from the main content blocks, it usually has such  blocks as navigation panels, copyright and privacy notices, and  advertisements (for business purposes and for easy user access).  We call these blocks that are not the main content blocks of the  page the noisy blocks. We show that the information contained in  these noisy blocks can seriously harm Web data mining.   Eliminating these noises is thus of great importance. In this paper,  we propose a noise elimination technique based on the following   observation: In a given Web site, noisy blocks usually share some   common contents and presentation styles, while the main content  blocks of the pages are often diverse in their actual contents  and/or presentation styles. Based on this observation, we propose  a tree structure, called Style Tree, to capture the common   presentation styles and the actual contents of the pages in a given  Web site. By sampling the pages of the site, a Style Tree can be  built for the site, which we call the Site Style Tree (SST). We  then introduce an information based measure to determine which  parts of the SST represent noises and which parts represent the  main contents of the site. The SST is employed to detect and  eliminate noises in any Web page of the site by mapping this page   to the SST. The proposed technique is evaluated with two data   mining tasks, Web page clustering and classification.   Experimental results show that our noise elimination technique is  able to improve the mining results significantly.   Categories and Subject Descriptors   H.3.3 [INFORMATION STORAGE AND RETRIEVAL]:   Information Search and Retrieval clustering, information   filtering, selection process.   General Terms   Algorith...
Mining data records in Web pages.
A large amount of information on the Web is contained in  regularly structured objects, which we call data records. Such  data records are important because they often present the essential  information of their host pages, e.g., lists of products or services.  It is useful to mine such data records in order to extract   information from them to provide value-added services. Existing  automatic techniques are not satisfactory because of their poor  accuracies. In this paper, we propose a more effective technique  to perform the task. The technique is based on two observations  about data records on the Web and a string matching algorithm.  The proposed technique is able to mine both contiguous and noncontiguous  data records. Our experimental results show that the  proposed technique outperforms existing techniques substantially.  Categories and Subject Descriptors   I.5 [Pattern Recognition]: statistical and structural   H.2.8 [Database Applications]: data mining   Keywords   Web data records, Web mining, Web information integration   1.# 
Mining topic%2Dspecific concepts and definitions on the web.
Traditionally, when one wants to learn about a particular topic,  one reads a book or a survey paper. With the rapid expansion of  the Web, learning in-depth knowledge about a topic from the Web  is becoming increasingly important and popular. This is also due  to the Webs convenience and its richness of information. In  many cases, learning from the Web may even be essential because  in our fast changing world, emerging topics appear constantly and  rapidly. There is often not enough time for someone to write a  book on such topics. To learn such emerging topics, one can  resort to research papers. However, research papers are often hard  to understand by non-researchers, and few research papers cover  every aspect of the topic. In contrast, many Web pages often  contain intuitive descriptions of the topic. To find such Web  pages, one typically uses a search engine. However, current  search techniques are not designed for in-depth learning. Top  ranking pages from a search engine may not contain any  description of the topic. Even if they do, the description is usually  incomplete since it is unlikely that the owner of the page has good  knowledge of every aspect of the topic. In this paper, we attempt  a novel and challenging task, mining topic-specific knowledge on   the Web. Our goal is to help people learn in-depth knowledge of a   topic systematically on the Web. The proposed techniques first  identify those sub-topics or salient concepts of the topic, and then  find and organize those informative pages, containing definitions  and descriptions of the topic and sub-topics, just like those in a  traditional book. Experimental results using 28 topics show that  the proposed techniques are highly effective.   Categories and Subject Descriptors   H.3.3 [Information S...
Scoring the Data Using Association Rules.
In many data mining applications, the objective is to select data cases of a target class.
A Neural Network Approach to Shape from Shading.
In this paper, we propose a method of recovering shape from shading that solves directly for the surface height using neural networks. The main motivation of this paper is to provide an answer to the open problem proposed by Zhou and Chellappa [11]. We first formulate the shape from shading problem by combining a triangular element surface model with a linearized reflectance map. Then, we use a linear feed-forward network architecture with six layers to compute the surface height with a singular value decomposition. The weights in the model initialized using eigenvectors and eigen-values of the stiffness matrix of objective functional. Experimental results show that our solution is very effective.
Advances in Knowledge Discovery and Data Mining

Using micro information units for internet search.
Internet search is one of the most important applications of the Web. A search engine takes the user’s keywords to retrieve and to rank those pages that contain the keywords. One shortcoming of existing search techniques is that they do not give due consideration to the micro-structures of a Web page. A Web page is often populated with a number of small information units, which we call micro information units (MIU). Each unit focuses on a specific topic and occupies a specific area of the page. During the search, if all the keywords in the user query occur in a single MIU of a page, the top ranking results returned by a search engine are generally relevant and useful. However, if the query words scatter at different MIUs in a page, the pages returned can be quite irrelevant (which causes low precision). The reason for this is that although a page has information on individual MIUs, it may not have information on their intersections. In this paper, we propose a technique to solve this problem. At the off-line preprocessing stage, we segment each page to identify the MIUs in the page, and index the keywords of the page according to the MIUs in which they occur. In searching, our retrieval and ranking algorithm utilizes this additional information to return those most relevant pages. Experimental results show that this method is able to significantly improve the search precision. 1.
Multivariate Time Series Prediction via Temporal Classification.
One of the important problems in many process industries is how to predict the occurrence of abnormal situations ahead of time in a multivariate time series environment. For example, in an oil refinery, hundreds of sensors (process variables) are installed at different sections of a process unit. These sensors constantly monitor the development of every stage of the process. Typically, each process variable (represented by a sensor) is given some value ranges, e.g., low, normal, and high. When the value of a variable reaches an undesirable range, e.g., low or high, an alarm is generated and displayed on a computer screen. The human operator, who monitors alarms, uses his/her experiences to decide what alarms are important and what actions to take. This manual process is acceptable for those non-critical variables. When
Speed%2Dup Iterative Frequent Itemset Mining with Constraint Changes.
Mining of frequent itemsets is a fundamental data mining task. Past research has proposed many efficient algorithms for the purpose. Recent work also highlighted the importance of using constraints to focus the mining process to mine only those relevant itemsets. In practice, data mining is often an interactive and iterative process. The user typically changes constraints and runs the mining algorithm many times before satisfied with the final results. This interactive process is very time consuming. Existing mining algorithms are unable to take advantage of this iterative process to use previous mining results to speed up the current mining process. This results in enormous waste in time and in computation. In this paper, we propose an efficient technique to utilize previous mining results to improve the efficiency of current mining when constraints are changed. We first introduce the concept of tree boundary to summarize the useful information available from previous mining. We then show that the tree boundary provides an effective and efficient framework for the new mining. The proposed technique has been implemented in the contexts of two existing frequent itemset mining algorithms, FP-tree and Tree Projection. Experiment results on both synthetic and reallife datasets show that the proposed approach achieves dramatic saving in computation.
Partially Supervised Classification of Text Documents.
We investigate the following problem: Given a set  of documents of a particular topic or class # , and a  large set # of mixed documents that contains documents  from class # and other types of documents,  identify the documents from class # in # . The key  feature of this problem is that there is no labeled non-  # document, which makes traditional machine learning  techniques inapplicable, as they all need labeled  documents of both classes. We call this problem partially  supervised classification. In this paper, we show  that this problem can be posed as a constrained optimization  problem and that under appropriate conditions,  solutions to the constrained optimization problem  will give good solutions to the partially supervised  classification problem. We present a novel technique  to solve the problem and demonstrate the effectiveness  of the technique through extensive experimentation.
A refinement approach to handling model misfit in text categorization.
Text categorization or classification is the automated assigning of text documents to pre-defined classes based on their contents. This problem has been studied in information retrieval, machine learning and data mining. So far, many effective techniques have been proposed. However, most techniques are based on some underlying models and/or assumptions. When the data fits the model well, the classification accuracy will be high. However, when the data does not fit the model well, the classification accuracy can be very low. In this paper, we propose a refinement approach to dealing with this problem of model misfit. We show that we do not need to change the classification technique itself (or its underlying model) to make it more flexible. Instead, we propose to use successive refinements of classification on the training data to correct the model misfit. We apply the proposed technique to improve the classification performance of two simple and efficient text classifiers, the Rocchio classifier and the nave Bayesian classifier. These techniques are suitable for very large text collections because they allow the data to reside on disk and need only one scan of the data to build a text classifier. Extensive experiments on two benchmark document corpora show that the proposed technique is able to improve text categorization accuracy of the two techniques dramatically. In particular, our refined model is able to improve the nave Bayesian or Rocchio classifier&#039;s prediction performance by 45% on average.
Querying multiple sets of discovered rules.
Rule mining is an important data mining task that has been applied to numerous real-world applications. Often a rule mining system generates a large number of rules and only a small subset of them is really useful in applications. Although there exist some systems allowing the user to query the discovered rules, they are less suitable for complex ad hoc querying of multiple data mining rulebases to retrieve interesting rules. In this paper, we propose a new powerful rule query language Rule-QL for querying multiple rulebases that is modeled after SQL and has rigorous theoretical foundations of a rule-based calculus. In particular, we first propose a rule-based calculus RC based on the first-order logic, and then present the language Rule-QL that is at least as expressive as the safe fragment of RC. We also propose a number of efficient query evaluation techniques for Rule-QL and test them experimentally on some representative queries to demonstrate the feasibility of Rule-QL.
Selector A Language Construct for Developing Dynamic Applications.

Discovering Frequent Substructures from Hierarchical Semi%2Dstructured Data.
Abstract: Frequent substructure discovery from a collection of semi-structured objects can serve for storage, browsing, querying, indexing and classification of semi-structured documents. This paper examines the problem of discovering frequent substructures from a collection of hierarchical semi-structured objects of the same type. The use of wildcard is an important aspect of substructure discovery from semi-structured data due to the irregularity and lack of fixed structure of such data. This paper proposes a more general and powerful wildcard mechanism, which allows us to find more complex and interesting substructures than existing techniques. Furthermore, the complexity of structural information of semi-structured data and the usage of wildcard make the existing frequent set mining algorithms inapplicable for substructure discovery. In this work, we adopt a vertical format for the storage of semi-structured objects, and adapt a frequent set mining algorithm for our purpose. The application of our approach to real-life data shows that it is very effective.
Visualizing web site comparisons.

Note on third%2Dorder boundary value problem for differential equations with deviating arguments.

Business applications of data mining.
y illustrative of the tremendous potential of KDD technology. 1.1 Risk Management and Targeted Marketing  Insurance and direct-mail retail are examples of businesses that rely on effective data analysis in order to make profitable business decisions. For example, insurers must be able to accurately assess the risks posed by policyholders in order to set insurance premiums at competitive levels. Overcharging low-risk policyholders would motivate such policyholders to seek lower premiums elsewhere. Undercharging high-risk policyholders would attract more high-risk policyholders because of the lower premiums. In both cases, costs would increase and profits would decrease. Effective data analysis leading to the creation of accurate predictive models is essential in order to address these issues.  In the case of direct-mail targeted marketing, retailers must be able to identify subsets of the population that are likely to respond to promotions in order to offset mailing and printing costs. 
Research Activities in Database Management and Information Retrieval at the University of Illinois at Chicago.

Efficiently Determine the Starting Sample Size for Progressive Sampling.
Given a large data set and a classification learning algorithm, Progressive Sampling (PS) uses increasingly larger random samples to learn until model accuracy no longer improves. It is shown that the technique is remarkably efficient compared to using the entire data. However, how to set the starting sample size for PS is still an open problem. We show that an improper starting sample size can still make PS expensive in computation due to running the learning algorithm on a large number of instances (of a sequence of random samples before achieving convergence) and excessive database scans to fetch the sample data. Using a suitable starting sample size can further improve the efficiency of PS. In this paper, we present a statistical approach which is able to efficiently find such a size. We call it the Statistical Optimal Sample Size (SOSS), in the sense that a sample of this size sufficiently resembles the entire data. We introduce an information-based measure of this resemblance (Sample Quality) to define the SOSS and show that it can be efficiently obtained in one scan of the data. We prove that learning on a sample of SOSS will produce model accuracy that asymptotically approaches the highest achievable accuracy on the entire data. Empirical results on a number of large data sets from the UCIKDD repository show that SOSS is a suitable starting size for Progressive Sampling.
Efficiently Determining the Starting Sample Size for Progressive Sampling.
Given a large data set and a classification learning algorithm, Progressive Sampling (PS) uses increasingly larger random samples to learn until model accuracy no longer improves. It is shown that the technique is remarkably efficient compared to using the entire data. However, how to set the starting sample size for PS is still an open problem. We show that an improper starting sample size can still make PS expensive in computation due to running the learning algorithm on a large number of instances (of a sequence of random samples before achieving convergence) and excessive database scans to fetch the sample data. Using a suitable starting sample size can further improve the efficiency of PS. In this paper, we present a statistical approach which is able to efficiently find such a size. We call it the Statistical Optimal Sample Size (SOSS), in the sense that a sample of this size sufficiently resembles the entire data. We introduce an information-based measure of this resemblance (Sample Quality) to define the SOSS and show that it can be efficiently obtained in one scan of the data. We prove that learning on a sample of SOSS will produce model accuracy that asymptotically approaches the highest achievable accuracy on the entire data. Empirical results on a number of large data sets from the UCIKDD repository show that SOSS is a suitable starting size for Progressive Sampling.
Analyzing the Interestingness of Association Rules from the Temporal Dimension.

Discovering unexpected information from your competitors%27 web sites.
Ever since the beginning of the Web, finding useful information from the Web has been an important problem. Existing approaches include keyword-based search, wrapper-based information extraction, Web query and user preferences. These approaches essentially find information that matches the user&#039;s explicit specifications. This paper argues that this is insufficient. There is another type of information that is also of great interest, i.e., unexpected information, which is unanticipated by the user. Finding unexpected information is useful in many applications. For example, it is useful for a company to find unexpected information about its competitors, e.g., unexpected services and products that its competitors offer. With this information, the company can learn from its competitors and/or design counter measures to improve its competitiveness. Since the number of pages of a typical commercial site is very large and there are also many relevant sites (competitors), it is very difficult for a human user to view each page to discover the unexpected information. Automated assistance is needed. In this paper, we propose a number of methods to help the user find various types of unexpected information from his/her competitors&#039; Web sites. Experiment results show that these techniques are very useful in practice and also efficient.  Keywords  Information interestingness, Web comparison, Web mining.  1. 
Identifying non%2Dactionable association rules.

Discovering the set of fundamental rule changes.
The world around us changes constantly. Knowing what has changed is an important part of our lives. For businesses, recognizing changes is also crucial. It allows businesses to adapt themselves to the changing market needs. In this paper, we study changes of association rules from one time period to another. One approach is to compare the supports and/or confidences of each rule in the two time periods and report the differences. This technique, however, is too simplistic as it tends to report a huge number of rule changes, and many of them are, in fact, simply the snowball effect of a small subset of fundamental changes. Here, we present a technique to highlight the small subset of fundamental changes. A change is fundamental if it cannot be explained by some other changes. The proposed technique has been applied to a number of real-life datasets. Experiments results show that the number of rules whose changes are unexplainable is quite small (about 20% of the total number of changes discovered), and many of these unexplainable changes reflect some fundamental shifts in the application domain.  Keywords: Change mining, data mining.  1. 
Intuitive Representation of Decision Trees Using General Rules and Exceptions.
Producing too many rules is a major problem with many  data mining techniques. This paper argues that one of the  key reasons for the large number of rules is that an  inefficient knowledge representation scheme has been used.  The current predominant representation of the discovered  knowledge is the if-then rules. This representation often  severely fragments the knowledge that exists in the data,  thereby resulting in a large number of rules. The  fragmentation also makes the discovered rules hard to  understand and to use. In this paper, we propose a more  efficient representation scheme, called general rules &amp;  exceptions. In this representation, a unit of knowledge  consists of a single general rule and a set of exceptions.  This scheme reduces the complexity of the discovered  knowledge substantially. It is also intuitive and easy to  understand. This paper focuses on using the representation  to express the knowledge embedded in a decision tree. An  algorithm that converts a de...
Clustering Through Decision Tree Construction.
this paper, we propose a novel clustering technique, which is based on a supervised learning technique called decision tree construction. The new technique is able to overcome many of these shortcomings. The key idea is to use a decision tree to partition the data space into cluster and empty (sparse) regions at different levels of details. The technique is able to find &#034;natural&#034; clusters in large high dimensional spaces efficiently. It is suitable for clustering in the full dimensional space as well as in subspaces. It also provides comprehensible descriptions of clusters. Experiment results on both synthetic data and real-life data show that the technique is effective and also scales well for large high dimensional datasets.
Web for Data Mining Applications.
A Recommender system is an intermediary program with user interface that automatically generates a list of information which suits an individual needs. Data Mining is the process of extracting patterns from data. Web data mining is the application of data mining techniques to discover patterns from the web. This article proposed a framework based on data mining technology for building a Web-page
Mining Changes for Real%2DLife Applications.
. Much of the data mining research has been focused on devising  techniques to build accurate models and to discover rules from databases.  Relatively little attention has been paid to mining changes in databases collected  over time. For businesses, knowing what is changing and how it has changed is  of crucial importance because it allows businesses to provide the right products  and services to suit the changing market needs. If undesirable changes are  detected, remedial measures need to be implemented to stop or to delay such  changes. In many applications, mining for changes can be more important than  producing accurate models for prediction. A model, no matter how accurate,  can only predict based on patterns mined in the old data. That is, a model  requires a stable environment, otherwise it will cease to be accurate. However,  in many business situations, constant human intervention (i.e., actions) to the  environment is a fact of life. In such an environment, building a pred...
Multi%2Dlevel organization and summarization of the discovered rules.
Many existing data mining techniques often produce a large number of rules, which make it very difficult for manual inspection of the rules to identify those interesting ones. This problem represents a major gap between the results of data mining and the understanding and use of the mining results. In this paper, we argue that the key problem is not with the large number of rules because if there are indeed many rules that exist in data, they should be discovered. The main problem is with our inability to organize, summarize and present the rules in such a way that they can be easily analyzed by the user. In this paper, we propose a technique to intuitively organize and summarize the discovered rules. With this organization, the discovered rules can be presented to the user in the way as we think and talk about knowledge in our daily lives. This organization also allows the user to view the discovered rules at different levels of details, and to focus his/her attention on those interes...
Exploration mining in diabetic patients databases findings and conclusions.
Real-life data mining applications are interesting because they often present a different set of problems for data miners. One such real-life application that we have done is on the diabetic patients databases. Valuable lessons are learnt from this application. In particular, we discover that the often neglected pre-processing and post-processing steps in knowledge discovery are the most critical elements in determining the success of a real-life data mining application. In this paper, we shall discuss how we carry out knowledge discovery on this diabetic patient database, the interesting issues that have surfaced, as well as the lessons we have learnt from this application. We will describe a semi-automatic means for cleaning the diabetic patient database, and present a step-by-step approach to help the health doctors explore their data and to understand the discovered rules better.  2  1. 
Targeting the right students using data mining.
The education domain offers a fertile ground for many interesting and challenging data mining applications. These applications can help both educators and students, and improve the quality of education. In this paper, we present a real-life application for the Gifted Education Programme (GEP) of the Ministry of Education (MOE) in Singapore. The application involves many data mining tasks. This paper focuses only on one task, namely, selecting students for remedial classes. Traditionally, a cut-off mark for each subject is used to select the weak students. That is, those students whose scores in a subject fall below the cut-off mark for the subject are advised to take further classes in the subject. In this paper, we show that this traditional method requires too many students to take part in the remedial classes. This not only increases the teaching load of the teachers, but also gives unnecessary burdens to students, which is particularly undesirable in our case because the GEP students are generally taking more subjects than non-GEP students, and the GEP students are encouraged to have more time to explore advanced topics. With the help of data mining, we are able to select the targeted students much more precisely.
Improving an Association Rule Based Classifier.
. Existing classification algorithms in machine learning mainly use heuristic  search to find a subset of regularities in data for classification. In the past  few years, extensive research was done in the database community on learning  rules using exhaustive search under the name of association rule mining. Although  the whole set of rules may not be used directly for accurate classification,  effective classifiers have been built using the rules. This paper aims to improve  such an exhaustive search based classification system CBA (Classification Based  on Associations). The main strength of this system is that it is able to use the  most accurate rules for classification. However, it also has weaknesses. This paper  proposes two new techniques to deal with these weaknesses. This results in  remarkably accurate classifiers. Experiments on a set of 34 benchmark datasets  show that on average the new techniques reduce the error of CBA by 17% and is  superior to CBA on 26 of the 34 dat...
Conceptual design issues and challenges.

Analyzing the Subjective Interestingness of Association Rules.
Association rules are a class of important regularities in databases. They are found to be very  useful in practical applications. However, association rule mining algorithms tend to produce  a huge number of rules, most of which are of no interest to the user. Due to the large number  of rules, it is very difficult for the user to analyze them manually in order to identify those  truly interesting ones. In this paper, we propose a new approach to assist the user in finding  interesting rules (in particular, unexpected rules) from a set of discovered association rules.  This technique is characterized by analyzing the discovered association rules using the user&#039;s  existing knowledge about the domain and then ranking the discovered rules according to  various interestingness criteria, e.g., conformity and various types of unexpectedness. This  technique has been implemented and successfully used in a number of applications.  Keywords: subjective interestingness, association rules, interestingness analysis in data mining.  1. 
Global%2Dlocal%2Dglobal method for logical structure extraction of form document image.


Web for Data Mining Organizing and Interpreting the Discovered Rules using the Web.
The web not only contains a vast amount of useful information, but also provides a powerful infrastructure for communication and information sharing. In this paper, we present a system (called DS-Web) that uses the web to help data mining. Specifically, we use the web to facilitate delivering and interpreting the discovered rules. Interpreting the discovered rules to gain a good understanding of the domain is an important phase of data mining. It is also a very difficult task because the number of rules involved is often very large. This problem has been regarded as a major obstacle to the use of data mining results. DS-WEB assists the user in understanding a set of discovered rules in two steps. First, it finds a special subset (or a summary) of the rules that represents the essential relationships of the domain to build a hierarchical structure of the rules. It then publishes this hierarchy of rules via multiple web pages connected using hyperlinks. By using the web, we inherit the a...
Clustering Transactions Using Large Items.
In traditional data clustering, similarity of a cluster of objects is measured by pairwise similarity of objects in that cluster. We argue that such measures are not appropriate for transactions that are sets of items. We propose the notion of large items, i.e., items contained in some minimum fraction of transactions in a cluster, to measure the similarity of a cluster of transactions. The intuition of our clustering criterion is that there should be many large items within a cluster and little overlapping of such items across clusters. We discuss the rationale behind our approach and its implication on providing a better solution to the clustering problem. We present a clustering algorithm based on the new clustering criterion and evaluate its e ectiveness. 1
Content%2Dbased Index and Retrieval Method of Chinese Document Images.

Pruning and Summarizing the Discovered Associations.
Association rules are a fundamental class of patterns that exist in data. The key strength of association rule mining is its completeness. It finds all associations in the data that satisfy the user specified minimum support and minimum confidence constraints. This strength, however, comes with a major drawback. It often produces a huge number of associations. This is particularly true for data sets whose attributes are highly correlated. The huge number of associations makes it very difficult, if not impossible, for a human user to analyze in order to identify those interesting/useful ones. In this paper, we propose a novel technique to overcome this problem. The technique first prunes the discovered associations to remove those insignificant associations, and then finds a special subset of the unpruned associations to form a summary of the discovered associations. We call this subset of associations the direction setting (DS) rules  as they set the directions that are followed by the...
Mining Association Rules with Multiple Minimum Supports.
Association rule mining is an important model in data mining. Its mining algorithms discover all item associations (or rules) in the data that satisfy the user-specified minimum support (minsup) and minimum confidence (minconf) constraints. Minsup controls the minimum number of data cases that a rule must cover. Minconf controls the predictive strength of the rule. Since only one minsup is used for the whole database, the model implicitly assumes that all items in the data are of the same nature and/or have similar frequencies in the data. This is, however, seldom the case in reallife applications. In many applications, some items appear very frequently in the data, while others rarely appear. If minsup is set too high, those rules that involve rare items will not be found. To find rules that involve both frequent and rare items, minsup has to be set very low. This may cause combinatorial explosion because those frequent items will be associated with one another in all possible ways. T...
Mining Interesting Knowledge Using DM%2DII.
1. Introduction Data mining aims to develop a new generation of tools tointelligently assist humans in analyzing mountains of data.
Visually Aided Exploration of Interesting Association Rules.
. Association rules are a class of important regularities in databases. They are found to be very useful in practical applications. However, the number of association rules discovered in a database can be huge, thus making manual inspection and analysis of the rules difficult. In this paper, we propose a new framework to allow the user to explore the discovered rules to identify those interesting ones. This framework has two components, an interestingness analysis component, and a visualization component. The interestingness analysis component analyzes and organizes the discovered rules according to various interestingness criteria with respect to the user&#039;s existing knowledge. The visualization component enables the user to visually explore those potentially interesting rules. The key strength of the visualization component is that from a single screen, the user is able to obtain a global and yet detailed picture of various interesting aspects of the discovered rules. Enhanced with co...

Interestingness%2DBased Interval Merger for Numeric Association Rules.
We present an algorithm for mining association rules from relational tables containing numeric and categorical attributes. The approach is to merge adjacentintervals of numeric values, in a bottom-up manner, on the basis of maximizing the interestingness of a set of association rules. A modi cation of the B-tree is adopted for performing this task e ciently. The algorithm takes O(kN) I/O time, where k is the number of attributes and N is the numberofrows in the table. We evaluate the e ectiveness of producing good intervals.
Integrating Classification and Association Rule Mining.
Classification rule mining aims to discover a small set of rules in the database that forms an accurate classifier. Association rule mining finds all the rules existing in the database that satisfy some minimum support and minimum confidence constraints. For association rule mining, the target of discovery is not pre-determined, while for classification rule mining there is one and only one predetermined target. In this paper, we propose to integrate these two mining techniques. The integration is done by focusing on mining a special subset of association rules, called class association rules (CARs). An efficient algorithm is also given for building a classifier based on the set of discovered CARs. Experimental results show that the classifier built this way is, in general, more accurate than that produced by the state-of-the-art classification system C4.5. In addition, this integration helps to solve a number of problems that exist in the current classification systems. Introduction ...
Using Decision Tree Induction for Discovering Holes in Data.
. Existing research in machine learning and data mining has been focused  on finding rules or regularities among the data cases. Recently, it was  shown that those associations that are missing in data may also be interesting.  These missing associations are the holes or empty regions. The existing algorithm  for discovering holes has a number of shortcomings. It requires each hole  to contain no data point, which is too restrictive for many real-life applications.  It also has a very high complexity, and produces a huge number of holes. Additionally,  the algorithm only works in a continuous space, and does not allow any  discrete/nominal attribute. These drawbacks limit its applications. In this paper,  we propose a novel approach to overcome these shortcomings. This approach  transforms the holes-discovery problem into a supervised learning task, and then  uses the decision tree induction technique for discovering holes in data.  1. Introduction  A company wants to profile its custo...
Concurrent Discretization of Multiple Attributes.
. Better decision trees can be learnt by merging continuous  values into intervals. Merging of values, however, could introduce inconsistencies  to the data, or information loss. When it is desired to maintain  a certain consistency, interval mergings in one attribute could disable  those in another attribute. This interaction raises the issue of determining  the order of mergings. We consider a globally greedy heuristic that  selects the &#034;best&#034; merging from all continuous attributes at each step.  We present an implementation of the heuristic in which the best merging  is determined in a time independent of the number of possible mergings.  Experiments show that intervals produced by the heuristic lead to improved  decision trees.  1 Introduction  1.1 Motivation  Continuous values, mainly reals and integers, are linearly ordered. Unlike discrete values, there could be many continuous values and each appears only a few times in the data. Directly applying induction algorithms designed ...
Discovering Interesting Holes in Data.
Current machine learning and discovery techniques focus on discovering rules or regularities that exist in data. An important aspect of the research that has been ignored in the past is the learning or discovering of interesting holes in the database. If we view each case in the database as a point in a it-dimensional space, then a hole is simply a region in the space that contains no data point. Clearly, not every hole is interesting. Some holes are obvious because it is known that certain value combinations are not possible. Some holes exist because there are insufficient cases in the database. However, in some situations, empty regions do carry important information. For instance, they could warn us about some missing value combinations that are either not known before or are unexpected. Knowing these missing value combinations may lead to significant discoveries. In this paper, we propose an algorithm to discover holes in databases. 1
Using General Impressions to Analyze Discovered Classification Rules.
One of the important problems in data mining is the evaluation of subjective interestingness of the discovered rules. Past research has found that in many real-life applications it is easy to generate a large number of rules from the database, but most of the rules are not useful or interesting to the user. Due to the large number of rules, it is difficult for the user to analyze them manually in order to identify those interesting ones. Whether a rule is of interest to a user depends on his/her existing knowledge of the domain, and his/her interests. In this paper, we propose a technique that analyzes the discovered rules against a specific type of existing knowledge, which we call general impressions, to help the user identify interesting rules. We first propose a representation language to allow general impressions to be specified. We then present some algorithms to analyze the discovered classification rules against a set of general impressions. The results of the analysis tell us ...
Forward and Backward Chaining in Constraint Programming %28Abstract%29.

Post%2DAnalysis of Learned Rules.
Rule induction research implicitly assumes that after producing the rules from a dataset, these rules will be used directly by an expert system or a human user. In real-life applications, the situation may not be as simple as that, particularly, when the user of the rules is a human being. The human user almost always has some previous concepts or knowledge about the domain represented by the dataset. Naturally, he/she wishes to know how the new rules compare with his/her existing knowledge. In dynamic domains where the rules may change over time, it is important to know what the changes are. These aspects of research have largely been ignored in the past. With the increasing use of machine learning techniques in practical applications such as data mining, this issue of post analysis of rules warrants greater emphasis and attention. In this paper, we propose a technique to deal with this problem. A system has been implemented to perform the post analysis of classificat...
Using Constraints to Model Disjunctions in Rule%2DBased Reasoning.

Intelligent Route Finding Combining Knowledge and Cases and an Efficient Search Algorithm.
: One of the major road transportation problems is route finding. With the massive and complicated road network of a modern city (or country), finding a good route to travel from one place to another is not a simple task. In Network Theory, this is a shortest path problem. Shortest path algorithms are often used to solve the problem. However, these algorithms are wasteful in terms of computation when applied to the route finding task. They may also produce routes that are not suitable for human drivers. Furthermore, finding a route only solves part of the route finding problem. Accepting user&#039;s feedback and learning from past experiences are also crucial to the success of a route finding system. In this paper, we present an integrated approach of using knowledge about the road network, past cases and an efficient search algorithm for route finding. This technique not only substantially reduces the time and space required in computation, but also produces humanoriented and personalized ...
An Improved Generic Arc Consistency Algorithm and Its Specializations.
Many general and specific arc consistency algorithms have been produced in the past for solving Constraint Satisfaction Problems (CSP). The important general algorithms are AC-3, AC-4, AC-5 and AC-6. AC-5 is also a generic algorithm. It can be reduced to AC-3, AC-4 and AC-6. Specific algorithms are efficient specializations of the general ones for specific constraints. Functional, anti-functional and monotonic constraints are three important classes of specific constraints. AC-5 has been specialized to produce an O(ed) algorithm (in time) for these classes of constraints. However, this specialization does not reduce the space requirement. In practical applications, both time and space requirements are important. This paper makes two contributions. First, it proposes an improved generic arc consistency algorithm, called AC-5*, which can be specialized to reduce both time and space complexities. Second, it presents a more efficient technique for handling an important subclass of function...
Recognition of 3D Objects from 2D Images %2D Some Issues.
This paper presents a simple methods for visualizing, understanding, interpreting, and recognizing 3D objects from 2D images. It extended the linear combination methods, uses parallel pattern matching and can handle 3D rigid concave objects as well convex objects and articulated objects, yet, needs only a very small number of learning samples. Some real images are illustrated, with future research discussed.
A Refinement Approach to Search and Constraint Satisfaction Problem.

Intelligent Air Travel and Tourist Information Systems.

Using Knowledge to Isolate Search in Route Finding.
Traveling is a part of every person&#039;s day-to-day life.  With the massive and complicated road network of a  modern city (or country), finding a good route to  travel from one place to another is not a simple task.  In Network Theory, this is the shortest path problem.  Shortest path algorithms are often used to solve the  problem. However, these algorithms are wasteful in  terms of computation when applied to the route  finding task. They may also produce solutions that are  not suitable for human drivers. In this paper, we  present an approach that uses knowledge about the  road network to substantially reduce the time and  space required in computation, and to ensure human  oriented solutions. Within this framework, three  alternative methods are proposed, which may be used  in different situations. A system has also been  implemented for route finding in Singapore.  1. Introduction  One of the important computer applications in the transportation industry is route finding. Suppose w...
Increasing Functional Constraints Need to Be Checked Only Once.
Central to solving Constraint Satisfaction Problem  (CSP) is the problem of consistency check. Past  research has produced many general and specific  consistency algorithms. Specific algorithms are  efficient specializations of the general ones for  specific constraints. Functional, anti-functional and  monotonic constraints are three important classes of  specific constraints. They form the basis of the current  constraint programming languages. This paper  proposes a more efficient method for checking an  important subclass of functional constraints,  increasing functional constraints. Rather than  checking them many times as in a typical consistency  check process, in the new method they (almost all of  them) only need to be checked once. This results in a  substantial saving in computation.  1. Introduction  The key technique in solving CSPs is consistency check. Arc consistency algorithms that work on a network representation of binary CSPs are perhaps the most important class of ...
Integrating Rules and Constraints.
A General Rule Markup Language has several purposes. It may serve as a lingua franca to exchange rules between different...
Finding the Shortest Route Using Cases%2C Knowledge%2C and Djikstra%27s Algorithm.

ConstraintLisp an object%2Doriented constraint programming language.

A Reinforcement Approach to Schelduling.

Scheduling via reinforcement.

